// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "leveldb/cache.h"

#include <cassert>
#include <cstdio>
#include <cstdlib>

#include "port/port.h"
#include "port/thread_annotations.h"
#include "util/hash.h"
#include "util/mutexlock.h"

namespace leveldb {

Cache::~Cache() {}

namespace {

// LRU cache implementation
//
// Cache entries have an "in_cache" boolean indicating whether the cache has a
// reference on the entry.  The only ways that this can become false without the
// entry being passed to its "deleter" are via Erase(), via Insert() when
// an element with a duplicate key is inserted, or on destruction of the cache.
//
// The cache keeps two linked lists of items in the cache.  All items in the
// cache are in one list or the other, and never both.  Items still referenced
// by clients but erased from the cache are in neither list.  The lists are:
// - in-use:  contains the items currently referenced by clients, in no
//   particular order.  (This list is used for invariant checking.  If we
//   removed the check, elements that would otherwise be on this list could be
//   left as disconnected singleton lists.)
// - LRU:  contains the items not currently referenced by clients, in LRU order
// Elements are moved between these lists by the Ref() and Unref() methods,
// when they detect an element in the cache acquiring or losing its only
// external reference.

// An entry is a variable length heap-allocated structure.  Entries
// are kept in a circular doubly linked list ordered by access time.
// LRUHandle简单理解就是哈希表HandleTable中每个slot就是LRUHandle的实例化对象。
// 双向链表和哈希表的基本构成单位，同时也是数据条目缓存和操作的基本单元
struct LRUHandle {
  void* value;  // 节点中保存的值，value是浅拷贝。
  void (*deleter)(const Slice&, void* value);  // 数据从Cache中清除时执行的清理函数；
  LRUHandle* next_hash;  // 哈希表HandleTable为了解决哈希冲突采用拉链法的链指针。
  // 节点在双向链表中的前驱后继节点指针，所有的cache数据都是存储在一个双向链表中。
  LRUHandle* next;  
  LRUHandle* prev;
  size_t charge;      // 当前LRUHandle所占用的内存大小。即当前节点占用的容量，LevelDB中每个节点容量为1。
  size_t key_length;  // 对应的key的长度。

  /*
   * 每个节点的in_cache变量值在如下几种情况下会置为false：
   *   1）删除该节点后。
   *   2）调用LRUCache的析构函数时，会将所有节点的in_cache置为false。
   *   3）插入一个节点时，如果已经存在一个键值相同的节点，则旧节点的in_cache会置为false。
   */
  bool in_cache;     // 该节点是否在缓存中，如果不在，则可以调用节点的销毁方法进行销毁。
  
  // 引用计数器，表示当前LRUHandle被引用的次数，包括LRUCache的引用。refs==1 && in_cache即说明该数据条目只被 LRUCache 引用了。
  /*
   * refs成员变量的变动规则如下。
   *   1）每次调用Ref函数，会将refs变量加1，调用Unref函数，会将refs变量减1。
   *   2）插入一个节点时，该节点会放到in_use_链表中，并且初始的引用计数为2，不再使用该节点时将引用计数减1，如果此时节点也不再被其他地方引用，那么引用计数为1，将其放到lru_链表中。
   *   3）查找一个节点时，如果查找成功，则调用Ref函数，将该节点的引用计数加1，如果引用计数大于等于2，会将节点放到in_use_链表中，同理，不再使用该节点时将引用计数减1，如果此时节点也不再被其他地方引用，那么引用计数为1，将其放到lru_链表中。
   */
  uint32_t refs;     
  uint32_t hash;     // key的hash值，该值缓存到此处可避免每次都进行哈希运算，提高效率。
  char key_data[1];  // key的起始位置。

  Slice key() const {  // key是深拷贝。
    // next is only equal to this if the LRU handle is the list head of an
    // empty list. List heads never have meaningful keys.
    assert(next != this);

    return Slice(key_data, key_length);
  }
};

// We provide our own simple hash table since it removes a whole bunch
// of porting hacks and is also faster than some of the built-in hash
// table implementations in some of the compiler/runtime combinations
// we have tested.  E.g., readrandom speeds up by ~5% over the g++
// 4.4.3's builtin hashtable.
class HandleTable {
 public:
  HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
  ~HandleTable() { delete[] list_; }

  LRUHandle* Lookup(const Slice& key, uint32_t hash) {
    return *FindPointer(key, hash);
  }

  LRUHandle* Insert(LRUHandle* h) {
    LRUHandle** ptr = FindPointer(h->key(), h->hash);
    LRUHandle* old = *ptr;
    h->next_hash = (old == nullptr ? nullptr : old->next_hash);
    *ptr = h;
    if (old == nullptr) {
      ++elems_;
      if (elems_ > length_) {
        // Since each cache entry is fairly large, we aim for a small
        // average linked list length (<= 1).
        Resize();
      }
    }
    return old;
  }

  LRUHandle* Remove(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = FindPointer(key, hash);
    LRUHandle* result = *ptr;
    if (result != nullptr) {
      *ptr = result->next_hash;
      --elems_;
    }
    return result;
  }

 private:
  // The table consists of an array of buckets where each bucket is
  // a linked list of cache entries that hash into the bucket.
  uint32_t length_;  // slot的数量
  uint32_t elems_;  // 已用slot的数量
  LRUHandle** list_;  // bucket数组

  // Return a pointer to slot that points to a cache entry that
  // matches key/hash.  If there is no such cache entry, return a
  // pointer to the trailing slot in the corresponding linked list.
  // 功能：根据key与其hash查找LRUHandle。
  // 如果key存在则返回其LRUHandle的指针，如果不存在则返回指向可插入的solt的指针。
  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = &list_[hash & (length_ - 1)];
    while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
      ptr = &(*ptr)->next_hash;
    }
    return ptr;
  }

  // 扩展哈希表。该方法会倍增solt大小，并重新分配空间。在重新分配solt的空间后，再对所有原有solt中的LRUHandle重哈希。最后释放旧的solt的空间。
  void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      new_length *= 2;
    }
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);
    uint32_t count = 0;
    for (uint32_t i = 0; i < length_; i++) {
      LRUHandle* h = list_[i];
      while (h != nullptr) {
        LRUHandle* next = h->next_hash;
        uint32_t hash = h->hash;
        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
        h->next_hash = *ptr;
        *ptr = h;
        h = next;
        count++;
      }
    }
    assert(elems_ == count);
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
  }
};

// A single shard of sharded cache.
// 使用数组+链表处理冲突定制了一个极简哈希表，便于控制分配以及伸缩。
// 多线程支持。为了提高并发，引入了分片；为了区分是否被客户端引用，引入两个双向链表。
// 使用两个双向链表将整个缓存分成两个不相交的集合：被客户端引用的 in-use 链表，和不被任何客户端引用的 lru_ 链表。
// 每个双向链表使用了一个空的头指针，以便于处理边界情况。并且表头的 prev 指针指向最新的条目，next 指针指向最老的条目，从而形成了一个双向环形链表。
// 使用 usage_ 表示缓存当前已用量，用 capacity_ 表示该缓存总量。
// 抽象出了几个基本操作：LRU_Remove、LRU_Append、Ref、Unref 作为辅助函数进行复用。
// 每个 LRUCache 由一把锁 mutex_ 守护。

class LRUCache {
 public:
  LRUCache();
  ~LRUCache();

  // 设置LRU Cache的容量大小。
  void SetCapacity(size_t capacity) { capacity_ = capacity; }

  // Like Cache methods, but with an extra "hash" parameter.
  // 只会从LRU链表中逐出LRUHandle，相当于in-use链表中的LRUHandle会被LRUCache “Pin”住，永远都不会逐出。
  // 对于LRUCache中的每个LRUHandle，其只有如下几种状态：
  //    对于还没存入LRUCache的LRUHandle，不在任一链表上（显然）。
  //    当前在LRUCache中，且正在被client使用的LRUHandle，在in-use链表上无序保存。
  //    当前在LRUCache中，当前未被client使用的LRUHandle，在LRU链表上按LRU顺序保存。
  //    之前在LRUCache中，但被用户通过Erase方法从LRUCache中删除，或用户通过Insert方法更新了该key的LRUHandle，或LRUCache被销毁时，LRUHandle既不在in-use链表上也不在LRU链表上。此时，该LRUHandle在等待client通过Release方法释放引用计数以销毁。
  Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,
                        size_t charge,
                        void (*deleter)(const Slice& key, void* value));
  Cache::Handle* Lookup(const Slice& key, uint32_t hash);  // 在哈希表中查找节点。
  void Release(Cache::Handle* handle);  // 在哈希表中释放一个节点的引用
  void Erase(const Slice& key, uint32_t hash);  // 在哈希表中移除一个节点
  void Prune();  // 将lru_双向链表中的节点全部移除
  size_t TotalCharge() const {
    MutexLock l(&mutex_);
    return usage_;
  }

 private:
  void LRU_Remove(LRUHandle* e);  //将一个节点从双向链表中移除
  void LRU_Append(LRUHandle* list, LRUHandle* e);  // 将一个节点插入list参数指定的双向链表
  void Ref(LRUHandle* e);  // 将LRUHandle的引用计数加一，并将其从lru_链表中转移到in_use_链表中；
  void Unref(LRUHandle* e);  // 将引用计数减一，当LRUHandle的引用计数减为1时，将其从in_use_链表中归还给lru_链表（其最后一个引用为链表指针的引用），当LRUHandle的引用计数减为0时，通过其deleter销毁该对象。
  bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);  // 移除一个节点

  // Initialized before use.
  size_t capacity_;  // 哈希表容量大小

  // mutex_ protects the following state.
  mutable port::Mutex mutex_;
  size_t usage_ GUARDED_BY(mutex_);  // 当前用量。

  // lru_.prev 指向最新的节点，lru_.next指向最旧的节点。如果一个节点的引用计数refs等于1并且未被移除，即节点的变量in_cache为true，则将该节点放到lru_双向链表中。
  LRUHandle lru_ GUARDED_BY(mutex_);  // 所有已经不再为客户端使用的条目都放在 lru 链表中，该链表按最近使用时间有序，当容量不够用时，会驱逐此链表中最久没有被使用的条目。

  // in_use_双向链表中的节点引用计数refs都大于等于2并且肯定未被移除，即节点的in_cache为true。
  // 所有正在被客户端使用的数据条目（an kv item）都存在该链表中，该链表是无序的，因为在容量不够时，此链表中的条目是一定不能够被驱逐的，因此也并不需要维持一个驱逐顺序。
  // 保存所有仍然被客户端引用的条目，由于在被客户端引用的同时还被缓存引用，肯定有 refs >= 2 和 in_cache==true.
  LRUHandle in_use_ GUARDED_BY(mutex_);  

  // HandleTable类型，该类型在LevelDB中定义了一个哈希表，成员变量包括哈希表的桶个数、元素个数、桶的首地址，成员方法包括在哈希表中插入、查找键以及哈希表的扩缩容方法。
  // 注意，在LRU Cache结构中操作哈希表的公共方法（Insert、Lookup等）实际都会调用table_变量中的相关插入和查找方法。
  HandleTable table_ GUARDED_BY(mutex_); // 实际使用的哈希表，LRU Cache对哈希表的操作都会通过底层的table_变量来操作。
};

LRUCache::LRUCache() : capacity_(0), usage_(0) {
  // Make empty circular linked lists.
  lru_.next = &lru_;
  lru_.prev = &lru_;
  in_use_.next = &in_use_;
  in_use_.prev = &in_use_;
}

LRUCache::~LRUCache() {
  assert(in_use_.next == &in_use_);  // Error if caller has an unreleased handle
  for (LRUHandle* e = lru_.next; e != &lru_;) {
    LRUHandle* next = e->next;
    assert(e->in_cache);
    e->in_cache = false;
    assert(e->refs == 1);  // Invariant of lru_ list.
    Unref(e);
    e = next;
  }
}

void LRUCache::Ref(LRUHandle* e) {
  //如果节点在lru_链表中，则调用Ref函数后会将节点从lru_链表中删除，并且放到in_use_链表中
  if (e->refs == 1 && e->in_cache) {  // If on lru_ list, move to in_use_ list.
    LRU_Remove(e);
    LRU_Append(&in_use_, e);
  }
  //将节点的refs变量加1
  e->refs++;
}

void LRUCache::Unref(LRUHandle* e) {
  assert(e->refs > 0);
  e->refs--;
  if (e->refs == 0) {  // 如果refs已经等于0，则删除并释放该节点。
    assert(!e->in_cache);
    (*e->deleter)(e->key(), e->value);
    free(e);
  } else if (e->in_cache && e->refs == 1) {  // 如果refs变量等于1并且in_cache为true，则将该节点从in_use_链表中删除并且移动到lru_链表中。
    // No longer in use; move to lru_ list.
    LRU_Remove(e);
    LRU_Append(&lru_, e);
  }
}

void LRUCache::LRU_Remove(LRUHandle* e) {
  e->next->prev = e->prev;
  e->prev->next = e->next;
}

void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {
  // Make "e" newest entry by inserting just before *list
  e->next = list;
  e->prev = list->prev;
  e->prev->next = e;
  e->next->prev = e;
}

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != nullptr) {
    Ref(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

void LRUCache::Release(Cache::Handle* handle) {
  MutexLock l(&mutex_);
  Unref(reinterpret_cast<LRUHandle*>(handle));
}

Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
                                size_t charge,
                                void (*deleter)(const Slice& key,
                                                void* value)) {
  MutexLock l(&mutex_);

  LRUHandle* e =
      reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  e->in_cache = false;
  e->refs = 1;  // for the returned handle.
  std::memcpy(e->key_data, key.data(), key.size());

  if (capacity_ > 0) {
    e->refs++;  // for the cache's reference.
    e->in_cache = true;
    LRU_Append(&in_use_, e);
    usage_ += charge;
    FinishErase(table_.Insert(e));
  } else {  // don't cache. (capacity_==0 is supported and turns off caching.)
    // next is read by key() in an assert, so it must be initialized
    e->next = nullptr;
  }
  while (usage_ > capacity_ && lru_.next != &lru_) {  // 当前已使用量大于设置的总容量且lru不为空，则会进行淘汰。
    LRUHandle* old = lru_.next;
    assert(old->refs == 1);
    bool erased = FinishErase(table_.Remove(old->key(), old->hash));  // 淘汰。
    if (!erased) {  // to avoid unused variable when compiled NDEBUG
      assert(erased);
    }
  }

  return reinterpret_cast<Cache::Handle*>(e);
}

// If e != nullptr, finish removing *e from the cache; it has already been
// removed from the hash table.  Return whether e != nullptr.
bool LRUCache::FinishErase(LRUHandle* e) {
  if (e != nullptr) {
    assert(e->in_cache);
    LRU_Remove(e);  // 从链表中删除节点e。
    e->in_cache = false;  // 将节点的in_cache置为false。
    usage_ -= e->charge;  // 修改当前已使用的容量大小。
    Unref(e);  // 对节点调用Unref函数。
  }
  return e != nullptr;
}

void LRUCache::Erase(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  FinishErase(table_.Remove(key, hash));
}

void LRUCache::Prune() {
  MutexLock l(&mutex_);
  while (lru_.next != &lru_) {
    LRUHandle* e = lru_.next;
    assert(e->refs == 1);
    bool erased = FinishErase(table_.Remove(e->key(), e->hash));
    if (!erased) {  // to avoid unused variable when compiled NDEBUG
      assert(erased);
    }
  }
}

static const int kNumShardBits = 4;
static const int kNumShards = 1 << kNumShardBits;  // LRU Cache工分为16个段。

/*
 * ShardedLRUCache中保存了若干个LRUCache，并根据插入的key的哈希将其分配到相应的LRUCache中。
 * 引入 SharedLRUCache 的目的在于减小加锁的粒度，提高读写并行度。策略比较简洁
 * 利用 key 哈希值的前 kNumShardBits = 4 个 bit 作为分片路由，可以支持 kNumShards = 1 << kNumShardBits 16 个分片。可以理解为有16个相同的LRU Cache结构，每次进行Cache操作时需要先去查找键属于的段。
 * 因为每个LRUCache有独立的锁，这种方式可以减少锁的争用，以优化并行程序的性能。
 */
class ShardedLRUCache : public Cache {
 private:
  LRUCache shard_[kNumShards];  // shard_成员的每个元素均为一个LRUCache结构。为了减小锁的粒度，LevelDB中通过哈希将键分为16个段，即shared_，每次进行Cache操作时需要先去查找键属于shared_中的哪一个。
  port::Mutex id_mutex_;  // ID锁，用于保护最后分配的ID（last_id_）。
  uint64_t last_id_;  // 最后分配的ID，用于给新的Handle对象分配唯一ID。

  // 对key进行一次哈希。
  static inline uint32_t HashSlice(const Slice& s) {
    return Hash(s.data(), s.size(), 0);
  }

  // 分配shard。将哈希得到的值右移28位，即取哈希值的高4位，因此通过Shard函数处理后的值小于16。
  static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }

 public:
  explicit ShardedLRUCache(size_t capacity) : last_id_(0) {  // capacity是16个LRU Cache的总容量。
    const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
    for (int s = 0; s < kNumShards; s++) {
      shard_[s].SetCapacity(per_shard);
    }
  }
  ~ShardedLRUCache() override {}
  Handle* Insert(const Slice& key, void* value, size_t charge,
                 void (*deleter)(const Slice& key, void* value)) override {
    const uint32_t hash = HashSlice(key);
    return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
  }
  Handle* Lookup(const Slice& key) override {
    const uint32_t hash = HashSlice(key);  // 对一个需要查找的字符串进行哈希。
    return shard_[Shard(hash)].Lookup(key, hash);  // 获取到一个键所属的段之后继续调用LRUCache结构的查找操作。
  }
  void Release(Handle* handle) override {
    LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
    shard_[Shard(h->hash)].Release(handle);
  }
  void Erase(const Slice& key) override {
    const uint32_t hash = HashSlice(key);
    shard_[Shard(hash)].Erase(key, hash);
  }
  void* Value(Handle* handle) override {
    return reinterpret_cast<LRUHandle*>(handle)->value;
  }
  uint64_t NewId() override {
    MutexLock l(&id_mutex_);
    return ++(last_id_);
  }
  void Prune() override {
    for (int s = 0; s < kNumShards; s++) {
      shard_[s].Prune();
    }
  }
  size_t TotalCharge() const override {
    size_t total = 0;
    for (int s = 0; s < kNumShards; s++) {
      total += shard_[s].TotalCharge();
    }
    return total;
  }
};

}  // end anonymous namespace

// 该函数返回一个ShardedLRUCache的实例，实例中有一个大小为16的shard_成员，shard_成员的每个元素均为一个LRUCache结构。
Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }

}  // namespace leveldb
